#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;


struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {};
};

//class Solution {
//public:
//    TreeNode* reConstructTree(vector<int>& preOrder, vector<int>& vinOrder, int& p, int q, int n)
//    {
//        if (p > preOrder.size() || q >= n)
//        {
//            return nullptr;
//        }
//        TreeNode* cur = nullptr;
//        int i = q;
//        for (; i < n; i++)
//        {
//            if (preOrder[p] == vinOrder[i])
//            {
//                cur = new TreeNode(preOrder[p]);
//                break;
//            }
//        }
//        if (cur == nullptr)
//        {
//            return nullptr;
//        }
//        ++p;
//        cur->left = reConstructTree(preOrder, vinOrder, p, q, i);
//        cur->right = reConstructTree(preOrder, vinOrder, p, i + 1, n);
//        return cur;
//    }
//    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
//        // write code here
//        int p = 0;
//        int q = 0;
//        int n = preOrder.size();
//        return reConstructTree(preOrder, vinOrder, p, q, n);
//    }
//};


int main()
{
    TreeNode* cur = nullptr;
    stack<TreeNode*> tree;
    tree.push(cur);
    cur = tree.top();
    return 0;
}

class Solution {
public:
    char* Serialize(TreeNode* root) {
        queue<TreeNode*> q;
        vector<char> ret;
        q.push(root);
        while (!q.empty())
        {
            TreeNode* cur = q.front();
            q.pop();
            if (!cur)
            {
                ret.push_back('#');
                continue;
            }
            ret.push_back(cur->val + '0');
            q.push(cur->left);
            q.push(cur->right);
        }
        int n = ret.size();
        char* arr = new char[n + 1];
        for (int i = 0; i < n; i++)
        {
            arr[i] = ret[i];
        }
        arr[n] = 0;
        return arr;
    }
    TreeNode* _Deserialize(char* str, int i, TreeNode*& phead, int n)
    {
        cout << i << " ";
        if (str[i] == '#' || i >= n)
        {
            i++;
            return nullptr;
        }
        TreeNode* cur = new TreeNode(str[i] - '0');
        if (phead == nullptr)
        {
            phead = cur;
        }
        cur->left = _Deserialize(str, i * 2 + 1, phead, n);
        cur->right = _Deserialize(str, i * 2 + 2, phead, n);
        return cur;
    }
    TreeNode* Deserialize(char* str) {
        int i = 0;
        int n = strlen(str);
        TreeNode* phead = nullptr;
        _Deserialize(str, i, phead, n);
        return phead;
    }
};


class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        // write code here
        if (root == nullptr)
        {
            return true;
        }
        vector<TreeNode*>ret;
        ret.push_back(root);
        int sum = 1;
        int i = 0;
        while (1)
        {
            TreeNode* cur = ret[i];
            i++;
            if (cur)
            {
                sum += 2;
                ret.push_back(cur->left);
                ret.push_back(cur->right);
            }
            if (i >= sum)
            {
                break;
            }
        }
        TreeNode* prev = nullptr;
        TreeNode* cur = ret[0];
        int n = ret.size();
        for (int i = 0; i < n; i++)
        {
            prev = cur;
            cur = ret[i];
            if (cur && prev == nullptr)
            {
                return false;
            }
        }
        return true;
    }
};


class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        // write code here
        if (root == nullptr)
        {
            return true;
        }
        queue<TreeNode*> q;
        q.push(root);
        TreeNode* prev = nullptr;
        TreeNode* cur = q.front();
        while (!q.empty())
        {
            prev = cur;
            cur = q.front();
            q.pop();
            if (cur && prev == nullptr)
            {
                return false;;
            }
            if (cur == nullptr)
            {
                continue;
            }
            q.push(cur->left);
            q.push(cur->right);
        }
        return true;
    }
};


class Solution {
public:
    TreeNode* reConstructTree(vector<int>& preOrder, vector<int>& vinOrder, int& p, int q, int n)
    {
        if (p > preOrder.size() || q >= n)
        {
            return nullptr;
        }
        TreeNode* cur = nullptr;
        int i = q;
        for (; i < n; i++)
        {
            if (preOrder[p] == vinOrder[i])
            {
                cur = new TreeNode(preOrder[p]);
                break;
            }
        }
        if (cur == nullptr)
        {
            return nullptr;
        }
        ++p;
        cur->left = reConstructTree(preOrder, vinOrder, p, q, i);
        cur->right = reConstructTree(preOrder, vinOrder, p, i + 1, n);
        return cur;
    }
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        // write code here
        int p = 0;
        int q = 0;
        int n = preOrder.size();
        return reConstructTree(preOrder, vinOrder, p, q, n);
    }
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        // write code here
        TreeNode* phead = reConstructBinaryTree(preOrder, inOrder);
        queue<TreeNode*> q;
        if (phead)
        {
            q.push(phead);
        }
        vector<int> ret;
        while (!q.empty())
        {
            int n = q.size();
            while (n)
            {
                TreeNode* cur = q.front();
                q.pop();
                if (n == 1)
                {
                    ret.push_back(cur->val);
                }
                if (cur->left)
                {
                    q.push(cur->left);
                }
                if (cur->right)
                {
                    q.push(cur->right);
                }
                n--;
            }
        }
        return ret;
    }
};